This relates to networks and, more particularly, to selecting a subset of network nodes from a given set of network nodes. It is applicable, for example, to monitoring the behavior of networks.
A data network such as the Internet comprises nodes (e.g., routers) and links that interconnect the nodes. A typical objective of such networks is to establish connections between nodes that utilize the network most effectively, which translates to the objective of choosing a best path from a given originating node of a connection to a given terminating node of the connection. One well known algorithm for choosing a path from an originating node to a terminating node is the Open Shortest Path First (OSPF) algorithm, where each link of the network has an associated cost; a path from node N1 to node N2 is said to have a cost that corresponds to the sum of the costs of the links which form the path, and the algorithm identifies a path that has the lowest cost.
There is a recognized need to know the operational state of the network—such as packet loss rate, packet delay through the routers and links, etc.—and to that end, there is a need to measure the traffic that flows through the various links and nodes. This need exists in the data network as a whole, and also in sub-networks of the data network, such as virtual private networks within a data network.
Whether it is the entire network or a sub-network, the situation typically is the same: an administrator desires to monitor a specific set of nodes (herein referred to as branch nodes) and is able to perform this monitoring through equipment or modules that the administrator is able to install in any of a given set of network nodes (herein referred to as potential monitoring nodes). The branch nodes and the potential monitoring nodes may or may not be disjoint; meaning that one or more of the potential monitoring nodes may also be branch nodes.
It would be beneficial to be able to choose a small set of nodes from among the set of potential monitoring nodes as the actual monitoring nodes.